package easy_diagonal

// S(1, 0) => 1
// S(M, 0) => M+1
// S(M, 1) => S(M-1, 1) + S(M-1, 0)
// S(M, N) = S(M-1, N) + S(M-1, N-1)
func Diagonal(n, p int) int {
	if p > 0 && n == p {
		return 1
	}
	if p == 0 && n > 0 {
		return n + 1
	}
	// var r1, r2 = int
	// if diagonal_cache(n-1, p) != 0 {
	//     r1 = diagonal_cache(n-1, p)
	// } else {
	//     r1 = Diagonal(n-1, p)
	//     diagonal_fill_cache(n-1, p, r1)
	// }
	// if diagonal_cache(n-1, p-1) !=0 {
	//     r2 = diagonal_cache(n-1, p-1)
	// } else {
	//     r2 = Diagonal(n-1, p-1)
	//     diagonal_fill_cache(n-1, p-1, r2)
	// }
	// return r1 + r2
	return Diagonal(n-1, p) + Diagonal(n-1, p-1)
}
